package Search;

import java.util.Arrays;
/*
适合数据量大，分布均匀的查找表
 */

public class InsertValueSearch {

  public static void main(String[] args) {

//    测试传统数组
    int[]num = new int[]{1,8,9,56,89};

    int[] arr = new int[100];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = i + 1;
    }
    System.out.println("原始数组:" + Arrays.toString(arr));

    int index = insertSearch(num, 0, num.length - 1,56);
    System.out.println("该数的下标为" + index);
  }

  public static int insertSearch(int[]arr,int left,int right,int findVal){
    System.out.println("count");
    //注意: findVal < arr[0]和findVal > arr[arr.length - 1]必须需要
    //否则我们得到的mid可能越界
    if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
      return -1;
    }

//    插值查找的重点，类似二分查找
    int mid = left + (right - left)*(findVal - arr[left]) / (arr[right] - arr[left]);
    int midVal = arr[mid];
    if (findVal > midVal) {
      return insertSearch(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) {
      return insertSearch(arr, left, right - 1, findVal);
    } else {
      return mid;
    }
  }
}
